/*
 * Copyright (c) 2018. J4dream created
 */

package com.j4dream.property.leetcode.basic;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

public class StringBasic {
    public String reverseString(String s) {
        //if ("".equals(s)) return s;
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length / 2; i++) {
            char t = chars[i];
            chars[i] = chars[chars.length - 1 - i];
            chars[chars.length - 1 - i] = t;
        }
        //String strRes = String.copyValueOf(chars);
        return new String(chars);
    }

    public int reverse(int x) {
        Long reverse = 0L;
        while (x != 0) {
            reverse = reverse * 10 + x % 10;
            x = x / 10;
        }
        if (reverse > Integer.MAX_VALUE || reverse < Integer.MIN_VALUE)
            return 0;
        return reverse.intValue();
    }

    //给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
    public int firstUniqChar(String s) {
        // 100 ms +  效率并不高
//        int foundIndex = -1;
//        Map<Character, Integer> cache = new HashMap<>();
//        for (int i = 0; i < s.length(); i++) {
//            if (cache.containsKey(s.charAt(i))) {
//                int val = cache.get(s.charAt(i));
//                cache.put(s.charAt(i), ++val);
//            } else {
//                cache.put(s.charAt(i), 1);
//            }
//        }
//
//        for (int j = 0; j < s.length(); j++) {
//            if(cache.get(s.charAt(j)) == 1) {
//                return j;
//            }
//        }
//
//        return foundIndex;

        int result = -1;
        for (char c = 'a'; c <= 'z'; c++) {
            int index = s.indexOf(c);
            if (index != -1 && index == s.lastIndexOf(c)) {
                result = result == -1 ? index : Math.min(index, result);
            }
        }
        return result;
    }

    //给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词。
    //你可以假设字符串只包含小写字母。
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        char[] charsArr1 = s.toCharArray();
        char[] charsArr2 = t.toCharArray();
//        Arrays.sort(charsArr1);
//        Arrays.sort(charsArr2);
//        for (int i = 0; i < s.length(); i++) {
//            if (charsArr1[i] != charsArr2[i]) {
//                return false;
//            }
//        }
        int[] validS = new int[26];
        int[] validT = new int[26];
        for (int i = 0; i < s.length(); i++) {
            validS[s.charAt(i) - 97]++;
            validT[t.charAt(i) - 97]++;
        }
        for (int j = 0; j < validS.length; j++) {
            if (validS[j] != validT[j]) return false;
        }

        return true;
    }

    //给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
    //
    //说明：本题中，我们将空字符串定义为有效的回文串。
    public boolean isPalindrome(String s) {
        s = s.toLowerCase();

        int x = 0, y = s.length() - 1;
        while (x < y) {
            if (s.charAt(x) < '0' || s.charAt(x) > 'z' || (s.charAt(x) > '9' && s.charAt(x) < 'a')) {
                x++;
            } else if (s.charAt(y) < '0' || s.charAt(y) > 'z' || (s.charAt(y) > '9' && s.charAt(y) < 'a')) {
                y--;
            } else {
                if (s.charAt(x) != s.charAt(y)) {
                    return false;
                }
                x++;
                y--;
            }

        }

        return true;
    }

    //实现 atoi，将字符串转为整数。
//在找到第一个非空字符之前，需要移除掉字符串中的空格字符。如果第一个非空字符是正号或负号，选取该符号，
//并将其与后面尽可能多的连续的数字组合起来，这部分字符即为整数的值。如果第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
//字符串可以在形成整数的字符后面包括多余的字符，这些字符可以被忽略，它们对于函数没有影响。
//当字符串中的第一个非空字符序列不是个有效的整数；或字符串为空；或字符串仅包含空白字符时，则不进行转换。
//若函数不能执行有效的转换，返回 0。
    public int myAtoi(String str) {
        long r = 0;
        int index = 0, flagNum = 1;
        boolean isNegatie = false;
        while (index < str.length() && str.charAt(index) == ' ') {
            index++;
        }
        if (index < str.length() && str.charAt(index) == '-') {
            isNegatie = true;
            index++;
        } else if (index < str.length() && str.charAt(index) == '+') {
            index++;
        }
        while (index < str.length() && Character.isDigit(str.charAt(index))) {
            // r = r * 10 + str.charAt(index) - 48;

            // 速度好像快一些
            r = r * 10 + str.charAt(index) - '0';
            if (r > Integer.MAX_VALUE) {
                return isNegatie ? Integer.MIN_VALUE : Integer.MAX_VALUE;
            }

            index++;
        }
        return isNegatie ? (int) -r : (int) r;
    }

    //实现 strStr() 函数。
    //
    //给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1
    public int strStr(String haystack, String needle) {
        // 可以调用系统。。。。
        //return haystack.indexOf(needle);

        // 可以优化空间很大。
        if (haystack.equals(needle) || "".equals(needle)) return 0;
        if (haystack.length() == 0 || haystack.length() < needle.length()) return -1;
        int foundIndex = -1, firstIndex = 0, secondIndex = 0;
        while (firstIndex < haystack.length()) {
            if (haystack.charAt(firstIndex) != needle.charAt(secondIndex)) {
                firstIndex++;
            } else {
                int sameCount = 0, preFirstIndex = firstIndex;
                while (secondIndex < needle.length() && firstIndex < haystack.length() && haystack.charAt(firstIndex) == needle.charAt(secondIndex)) {
                    firstIndex++;
                    secondIndex++;
                    sameCount++;
                }
                if (sameCount == needle.length()) {
                    return firstIndex - sameCount;
                } else {
                    secondIndex = 0;
                    firstIndex = preFirstIndex + 1;
                }
            }

        }
        return foundIndex;
    }

    // 报数序列是指一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：
    public String countAndSay(int n) {
        if (n <= 1) return "1";
        StringBuffer sb = new StringBuffer("1");
        for (int j = 0; j < n - 1; j++) {
            StringBuffer temp = new StringBuffer();
            for (int k = 0; k < sb.length(); k++) {
                char c = sb.charAt(k);
                char countC = '1';
                while (k + 1 < sb.length() && sb.charAt(k + 1) == sb.charAt(k)) {
                    k++;
                    countC++;
                }
                temp.append(countC);
                temp.append(c);
            }
            sb = temp;
        }
        return sb.toString();
    }
    //最长公共前缀
    //编写一个函数来查找字符串数组中的最长公共前缀。
    //
    //如果不存在公共前缀，返回空字符串 ""。
    public String longestCommonPrefix(String[] strs) {
//        int count=strs.length;
//        String prefix="";
//        if(count!=0){
//            prefix=strs[0];
//        }
//        for(int i=0;i<count;i++){
//            while(!strs[i].startsWith(prefix)){
//                    prefix=prefix.substring(0,prefix.length()-1);
//            }
//        }
//        return prefix;

        if (strs.length == 0) return "";
//        int minLength = strs[0].length();
//        int minIndex = 0;
//        for (int i = 1; i < strs.length; i++) {
//            if (strs[i].length() < minLength) {
//                minIndex = i;
//                minLength = strs.length;
//            }
//        }
        String prefix = strs[0];
        for (int j = 0; j < strs.length; j++) {
            while (!strs[j].startsWith(prefix))
                prefix = prefix.substring(0, prefix.length() -1);
        }

        return prefix;
    }
}
